/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(!head)  return NULL;
        /*
        每次新建一个节点主要需确立其next、random两个指针，难点在于确定random指针；
        可考虑“分治”，先复制完next，整个链表复制完之后再考虑确定random指针.
        时间复杂度：O(n*n)
        */
        Node* newHead = new Node(head->val);
        Node* pNewHead = newHead;
        Node* pHead = head;
        vector<Node*> newList;  //存储新链表各节点位置
    
        //先复制next信息
        while(pHead->next){
            pNewHead->next = new Node(pHead->next->val);
            pNewHead = pNewHead->next;
            pHead = pHead->next;
        }

        //通过取得原链表random的相对位置来确定新链表的random
        pHead = head;
        pNewHead = newHead;
        while(pHead){
            //若原链表中节点的random为NULL,则新链表同理亦是
            if(!pHead->random){
                pNewHead->random = NULL;
                pHead = pHead->next;
                pNewHead = pNewHead->next;
                continue;
            }
            Node* headLocation = head;
            Node* newHeadLoction = newHead;
            while(headLocation){
                if(headLocation == pHead->random)  break;
                headLocation = headLocation->next;
                newHeadLoction = newHeadLoction->next;
            }
            //默认一定能找到random节点
            pNewHead->random = newHeadLoction;
            pNewHead = pNewHead->next;
            pHead = pHead->next;
        }

        return newHead;
    }
};

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(!head)  return NULL;
        /*
        每次新建一个节点主要需确立其next、random两个指针，难点在于确定random指针；
        可考虑“分治”，先复制完next，整个链表复制完之后再考虑确定random指针.
        时间复杂度：O(n*n)
        优化：使用哈希表能在O(1)时间内找到原链表中phead对应的pNewHeead(优化random指针的确定过程),以空间换时间
        */
        Node* newHead = new Node(head->val);
        Node* pNewHead = newHead;
        Node* pHead = head;
        unordered_map<Node*, Node*> umNode;  //用于存储<pHead,pNewHead>配对信息
        umNode[head] = pNewHead;

        //先复制next信息
        while(pHead->next){
            pNewHead->next = new Node(pHead->next->val);             
            pNewHead = pNewHead->next;                                          
            pHead = pHead->next;
            umNode[pHead] = pNewHead;
        }

        pHead = head;
        pNewHead = newHead;
        while(pHead){
            if(!pHead->random){
                pNewHead->random = NULL;
            }else{
                auto x = umNode.find(pHead->random);
                pNewHead->random = x->second;
            }
            pHead = pHead->next;
            pNewHead = pNewHead->next;
        }

        return newHead;
    }
};

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(!head)  return NULL;
        /*
        每次新建一个节点主要需确立其next、random两个指针，难点在于确定random指针；
        可考虑“分治”，先复制完next，整个链表复制完之后再考虑确定random指针.
        时间复杂度：O(n*n)
        优化：使用哈希表能在O(1)时间内找到原链表中phead对应的pNewHeead(优化random指针的确定过程),以空间换时间
        进一步优化：通过观察发现，将新复制的节点pCloned插入pHead后面，再设置新节点的random指针
        */
        Node* pHead = head;
        while(pHead){
            Node* pCloned  = new Node(pHead->val);
            pCloned->next = pHead->next;
            pCloned->random = NULL;

            pHead->next = pCloned;  //新节点链接到原节点后面
            pHead = pCloned->next;   
        }

        //设置pClonedderandom指针
        pHead = head;
        while(pHead){
            Node* pNewHead = pHead->next;
            if(pHead->random){
                pNewHead->random = pHead->random->next;
            } 
            pHead = pNewHead->next;
        }

        //拆分两个链表
        pHead = head;
        Node* newHead = head->next;
        Node* pNewHead = newHead;
        while(pHead){
            pHead->next = pNewHead->next;
            pHead = pHead->next;
            if(pHead){
                pNewHead->next = pHead->next;
                pNewHead = pNewHead->next;
            }
        }

        return newHead;
    }
};